Namespacing everything to /UVa.
[andmenj-acm.git] / UVa / 116 - Undirectional TSP / 116.cpp
blobb2621a18832bb0471115710aaaff3d97a5220476
1 #include <iostream>
2 #include <vector>
4 using namespace std;
6 int main(){
7 int rows, cols;
8 while(cin >> rows >> cols){
9 //g = matriz de entrada
10 long long g[rows][cols];
11 //dp[i][j] = minimo peso para llegar a la casilla (i,j)
12 //empezando en cualquiera de la Ășltima columna
13 long long dp[rows][cols];
14 //p[i][j] = Fila en la que estuve antes de llegar a la casilla
15 //(i,j), pero recorriendo la matriz de derecha a izquierda
16 int p[rows][cols];
17 for (int i=0; i<rows; ++i){
18 for (int j=0; j<cols-1; ++j){
19 cin >> g[i][j];
20 dp[i][j] = LLONG_MAX;
21 p[i][j] = -1;
23 cin >> g[i][cols-1];
24 dp[i][cols-1] = g[i][cols-1];
25 p[i][cols-1] = -1;
28 for (int j=cols-2; j>=0; --j){
29 for (int i=0; i<rows; ++i){
30 int previousRows[] = {(i+rows-1)%rows, i, (i+1)%rows };
31 sort(previousRows, previousRows + 3);
32 for (int k=0; k<3; ++k){
33 if (dp[previousRows[k]][j+1] < dp[i][j]){
34 dp[i][j] = dp[previousRows[k]][j+1];
35 p[i][j] = previousRows[k];
38 dp[i][j] += g[i][j];
42 long long minWeight = LLONG_MAX, firstRow = -1;
43 for (int i=0; i<rows; ++i){
44 if (dp[i][0] < minWeight){
45 firstRow = i;
46 minWeight = dp[i][0];
50 vector<int> path;
51 int i = firstRow;
52 int j = 0;
53 while (j < cols-1){
54 path.push_back(p[i][j]);
55 i = p[i][j];
56 ++j;
59 cout << firstRow + 1;
60 for (int i=0; i<path.size(); ++i){
61 cout << " " << path[i] + 1;
63 cout << endl;
64 cout << minWeight << endl;
66 return 0;